package com.example.leetdemo.process;


import java.util.*;

public class Solution687 {

    public int longestUnivaluePath(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int height = 0;
        Set<TreeNode> set = new HashSet<>();
        List<TreeNode> list = new ArrayList<>();
        list.add(root);
        while (list.size() > 0) {
            List<TreeNode> list1 = new ArrayList<>();
            for (TreeNode treeNode : list) {
                if (!set.contains(treeNode)) {
                    height = Math.max(height, heightUnivalue(treeNode, set, false));
                }
                if (treeNode.left != null) {
                    list1.add(treeNode.left);
                }
                if (treeNode.right != null) {
                    list1.add(treeNode.right);
                }
            }
            list = list1;
        }
        return height;
    }


    private int heightUnivalue(TreeNode parent, Set<TreeNode> set, Boolean hasRoot) {
        int value = parent.val;
        int height = 0;
        set.add(parent);
        if (parent.left != null && parent.right != null
                && parent.right.val == value && parent.right.val == parent.left.val) {
            if (hasRoot) {
                int left = heightUnivalue(parent.left, set, hasRoot) + 1;
                int rigth = heightUnivalue(parent.right, set, hasRoot) + 1;
                if(height < left && height < rigth) {
                    height = left + rigth;
                } else{
                    height = Math.max(left, rigth) + 1 + height;
                }

            } else {
                height = height + 1 + heightUnivalue(parent.left, set, true);
                height = height + 1 + heightUnivalue(parent.right, set, true);
            }
        } else {
            if (parent.left != null && parent.left.val == value) {
                height = height + 1 + heightUnivalue(parent.left, set, true);
            }
            if (parent.right != null && parent.right.val == value) {
                height = height + 1 + heightUnivalue(parent.right, set, true);
            }
        }


        return height;
    }

    static class TreeNode {
        Integer val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(Integer val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        TreeNode treeNode7 = new TreeNode(1);
        TreeNode treeNode6 = new TreeNode(1);
        TreeNode treeNode5 = new TreeNode(1);
        TreeNode treeNode4 = new TreeNode(1);

        TreeNode treeNode3 = new TreeNode(1, treeNode6, treeNode7);
//        TreeNode treeNode2 = new TreeNode(null, treeNode4, treeNode5);
        TreeNode treeNode1 = new TreeNode(1, null, treeNode3);

        Solution687 solution687 = new Solution687();
        System.err.println(solution687.longestUnivaluePath(treeNode1));
    }
}
